1. Field of the Invention
The present invention generally relates to interconnection systems wherein a large number of sources are selectively connected to a large number of destinations. A specific application of such an interconnection system is in a shared-memory computer system. More particularly, the invention is directed to a multipath network hierarchy having two or more levels of multistage networks with different message transfer latencies.
2. Description of the Prior Art
Prior art shared-memory systems having large number of processors are typically interconnected with a multistage network. By a large number of processors, what is meant is a number of processors of, say, on the order of 256 or greater. In at least one example of a high performance multiprocessor system, the network was built with a technology ten times faster than the technology of the processors in order to overcome the transfer delays which are inherent in a multistage network architecture. The performance limitations of multistage networks have led to the invention of hierarchical networks as disclosed, for example, in U.S. Pat. No. 4,752,777 to Franaszek and copending application Ser. No. 07/125,088 and described in an article entitled "Path Hierarchies in Interconnection Networks" by Peter A. Franaszek published in the IBM Journal of Research and Development, vol. 31, no. 1, Jan. 1987, pp. 120-131.
The operation of a hierarchical network is analogous to that of a storage hierarchy, whose average performance in a good design is largely determined by the speed of the fastest component. The path hierarchy described in U.S. Pat. No. 4,752,777 has only two levels, the top level or fast path being provided by a crossbar switch. Path hierarchies, however, need not necessarily be limited to two levels or include a crossbar switch. If, for example, a network hierarchy is configured with multiple levels of multistage networks, each one with different message transfer latencies, significant cost advantages could be achieved over a two level hierarchy with a crossbar switch. Furthermore, in cases where the number N of network nodes is very large, for example, where N is larger than 1000, the only type of hierarchy technology that could actually be realized under current technology would be one consisting of multistage networks only, given the hardware complexity of a crossbar switch, which grows quadratically with N.